#ifndef _SEQUENCES_H_
#define _SEQUENCES_H_

#include "util.h"
#include "interpret.h"
#include "graphdl.h"
#include <vector>
#include <sstream>
#include <fstream>
#include <pthread.h>

// all this for turning "stripped" into sequences.bin"
struct Sequence {
  int32 id_;
  vector<int64> v_;  
  string ToString() {
    ostringstream ostr;
    ostr << id_ << "   " << v_.size() << "   ";
    for (uint32 i=0; i<v_.size(); i++) ostr << v_[i] << " ";
    return ostr.str();
  }
};
// read a sequence from "stripped"
bool LoadSequence(istream &in, Sequence & s);
bool operator <(const Sequence &a, const Sequence &b);
bool IsPrefix(const Sequence &a, const Sequence &b);
bool operator ==(const Sequence &a, const Sequence &b);
inline uint64 TrainingPortion(uint64 length) { return length - 1;}

struct SequenceIndex {
  template <class F> // 

  // returns (-1, -1) if no mostly matching sequences
  // returns id of matching sequence (one that matches training portion).
  // second value is 1 if correct, 0 if incorrect
  pair<int32, int32> Search(F & f) {
    int32 low = 0;
    int32 high = num_sequences_;
    uint32 x = 0;
    int32 seq = -1;
    while (high > low) {
      // cout << "x = " << x << " high = " << high << " low = " << low << endl;
      if ((x >= 3) && (TrainingPortion(lengths_[low]) == x)) {
	seq = low;
	break;
      }
      int64 rv = f(x);
      // cout << "rv = " << rv << endl; 
      low = FindBoundary(low, high, x, rv);
      high = FindBoundary(low, high, x, rv+1);
      x++;
    }
    if (seq == -1) return make_pair(-1, -1);
    pair<int32, int32> ret(seq, 1);
    for (; (int32)x<lengths_[seq]; x++) {
      if (f(x) != sequences_[seq][x]) {
	ret.second = 0;
	break;
      }
    }
    return ret;    
  }
  
  // finds the first sequence index i between low and high inclusive
  //    such that sequences_[i][x] >= y 
  int32 FindBoundary(int32 low, int32 high, int32 x, int64 y) {
    while (high > low) {
      int32 mid = (low + high) / 2;
      if (lengths_[mid] > x && sequences_[mid][x] >= y) 
	high = mid;
      else low = mid + 1;
    }
    return low;
  }

  char * GetDescription(int32 sequence_num) {
    return descriptions_[sequence_num];
  }
  
  int64 GetNumSequences() { return num_sequences_; }
  int64* GetSequence(int32 id) { return sequences_[id]; }
  int32 GetSequenceLength(int32 id) { return lengths_[id]; }

  // TODO: we might want to free memory on destruction

  void Load();
  int32 num_sequences_;
  int32 * original_ids_; // not actually used for anything
  int32 * lengths_;
  int64 ** sequences_;
  char ** descriptions_;
};


struct SequenceSearch : public AllocatorDependant, public Tester {
  SequenceIndex index_;
  pthread_mutex_t lock_;
  pair<uint64, pair<int32, int32> > * code_seq_cache_;
  uint64 cache_size_;
  ofstream store_;
  GraphDL gdl_;
  int64 dl_;

  virtual int32 NumShards() { return 1; } 
  virtual void FlagReferences(int32 shard, Frontier * frontier);
  virtual void ObjectsDeleted(int32 shard);

  SequenceSearch();
  
  ~SequenceSearch() {
    delete [] code_seq_cache_;
  }

  struct SeqInfo {
  SeqInfo() : code_(NULL), original_dl_(0), correct_(false) {}
    Object * code_;
    uint64 original_dl_;
    bool correct_;
  };
  SeqInfo * seq_info_;
  
  uint64 num_correct_;
  uint64 num_predicted_;

  vector<bool> ever_matched_;
  uint64 new_matches_this_run_;

  // Handles changes to the gdl and utility_
  void CheckEverMatched(uint64 id) {
    if (!ever_matched_[id]) {
      cout << "New match id:" << id << endl;
      ever_matched_[id] = true;
      new_matches_this_run_++;
    }    
  }

  void SetSeqInfo(uint64 id, Object * code, bool correct) {
    SeqInfo & ref = seq_info_[id];
    dl_ -= gdl_.dl_;
    if (ref.code_) {
      gdl_.RemoveObject(ref.code_);
    } else {
      dl_ -= ref.original_dl_;
    }
    if (code) {
      gdl_.AddObject(code);
    } else {
      dl_ += ref.original_dl_;
    }
    num_correct_ -= (ref.correct_ ? 1 : 0);
    num_predicted_ -= (ref.code_ ? 1 : 0);
    ref.code_ = code;
    ref.correct_ = correct;
    num_correct_ += (ref.correct_ ? 1 : 0);
    num_predicted_ += (ref.code_ ? 1 : 0);
    dl_ += gdl_.dl_;
  }
  
  uint64 NumSequences() { return index_.num_sequences_;}

  // Which sequence do you match, and is it correct
  pair<int32, int32> CodeToSequence(Object *& code, Vinterpreter *interp);

  // returns a new utility
  double Test(Object *&code, Vinterpreter *interp_, bool update);
  Object * Data(Object *&param, ThreadAllocator *a);

  int SequencesFound() { return num_predicted_; }

  string StoreFileName() { return "store/seq-code";}
  void LoadState(ThreadAllocator *ta);
};


// A functor that runs a function from integer to integer via interpretation
struct Interpret {
  Object ** code_;
  Vinterpreter *interp_;
  int64 operator () (int64 x) {
    Object * arg = MakeInteger(x);
    Object * call_code = interp_->a_->MakeArray(2, code_, &arg);
    ObjectSaver s_call_code(interp_->a_, &call_code);
    Object * result 
      = interp_->SafeExecute(call_code, (5000 * (x + 1)));
    if (result && GetType(result) == INTEGER) return GetInteger(result);
    // Return a useless number if there was a problem.
    return 0xDEADBEEF;
  }
};

void MakeBinarySequenceFile();

int sequences_main();

#endif
